package slidewindow.窗口长度可变的滑动窗口题目;

import java.util.HashMap;
import java.util.Map;

// 窗口大小不固定类型的滑动窗口  双while来解决   右指针右移  左指针压缩
class 最小覆盖字串_76_重做版 {
            public String minWindow(String s, String t) {

                //                      长度不固定的子串 结果双指针来保存
                int left = 0, right = 0, resLeft = 0, resRight = Integer.MAX_VALUE;
                Map<Character, Integer> tMinusS = new HashMap<>();
                for(Character c:t.toCharArray()) {
                    tMinusS.put(c, tMinusS.getOrDefault(c, 0) + 1);
                }

                while(right < s.length()) {
                    // 需要对比两个窗口中  每个元素是否个数一致   可以保存 t中字符比s中字符多的个数
                    // 原始如需要的字符个数为  a:3 b:4  right 出现了 a  a就减一  left出现了a  窗口右移 后 a就加一
                    Character rChar = s.charAt(right);
                    if(tMinusS.containsKey(rChar)) tMinusS.put(rChar, tMinusS.get(rChar) - 1);

                    while(sSameCntWithT(tMinusS)) {
                        if(right - left < resRight - resLeft) { // 更新结果的左右指针
                            resRight = right;
                            resLeft = left;
                        }
                        Character lChar = s.charAt(left);
                        if(tMinusS.containsKey(lChar)) tMinusS.put(lChar, tMinusS.get(lChar) + 1);
                        left ++;
                    }
                    right++;
                }
                return resRight == Integer.MAX_VALUE ? "" : s.substring(resLeft, resRight + 1); // substring 左闭右开
            }

            private boolean sSameCntWithT(Map<Character, Integer> tMinusS) {
                for(Integer i : tMinusS.values()) {
                    // 可能出现负数  如 s a   t  aa  两次-1 变成了  -1 所以不能用 i == 0 来判断
                    if(i > 0) return false;
                }
                return true;
            }
        }
